package com.yxp.offer;

/**
 * @author : yang.xp
 * @date : 2021/8/20 9:53
 * @description : 剑指 Offer 63. 股票的最大利润
 * 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
 * [7,1,5,3,6,4]
 */
public class Problem63 {
    public static void main(String[] args) {
        int[] prices = new int[]{7, 2, 100, 1, 10, 4};
        Problem63 problem63 = new Problem63();
        System.out.println(problem63.maxProfit(prices));
    }

    /**
     * 滑动窗口？
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int minPrice = prices[0];
        int res = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else {
                res = Math.max(res, prices[i] - minPrice);
            }
        }
        return res;
    }


    /**
     * 执行用时：
     * 344 ms
     * , 在所有 Java 提交中击败了
     * 5.01%
     * 的用户
     * 内存消耗：
     * 38.2 MB
     * , 在所有 Java 提交中击败了
     * 42.46%
     * 的用户
     * @param prices
     * @return
     */
    public int maxProfit1(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int minPrice = prices[0];
        int res = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            }
            for (int j = i; j < prices.length; j++) {
                if (prices[j] > minPrice) {
                    int tempRes = prices[j] - minPrice;
                    if (tempRes > res) {
                        res = tempRes;
                    }
                }
            }
        }
        return res;
    }
}
